A communications network 10 is depicted in FIG. 1. The network 10 has a number of switches A,B,C,D,E,F,G,H,I which are interconnected to one another by trunks or buses 11. Individual units of customer premises equipment or terminals 12 or 16 at individual sites or subscriber locations 19 or 20, respectively, are connected to particular switches A or I via a subscriber loop or communication link 14 or 18.
A call originating at the subscriber location 19 and destined for the subscriber location 20 is transmitted to the local switch A via the subscriber loop 14. From the switch A the call may be routed to the switch E, from the switch E to the switch F and from the switch F to the switch I. At the switch I, the call is transmitted to the subscriber location 19 via the subscriber loop 18.
Illustratively, calls transmitted between switches may be organized into packets. An illustrative packet is shown in FIG. 2. As depicted, the packet is a data structure containing a header and user data. The header may include a destination address which typically is simply the identification number of a site and a particular user or telephone number of the called subscriber location. The user data portion contains the information of the call.
The central function of any communications network switch, such as the switches A-I, is to route a call or packet to the appropriate destination. When a call or packet is received at the switch I, its destination address is determined. Next, the switch I routes the call or packet to an output port designated to calls with the particular destination address of the call or packet. FIG. 3 depicts a switch 50 having a plurality of input ports 51-1, 51-2, . . . , 51-n and a plurality of output ports 52-1, 52-2, . . . , 52-n. Calls or packets originating at a subscriber line or another switch are received at one of the input ports 51-1, 51-2, . . . , 51-n. Such calls or packets are outputted onto the appropriate output port 52-1, 51-2, . . . , 52-n depending on the destination address of the call or packet.
For purposes of convenience, hierarchical switching is discussed below using the example of a telephone network with central office switches. However, the discussion applies analogously to other communication networks such as private branch exchange networks (PBX's) or local area networks (LANs).
In the United States, each subscriber location has a telephone number comprising an area code (three digits) a local exchange or NNX number (three digits) and a subscriber line number (four digits). Consider the case where the subscriber location 20 has the area code "abc", the NNX number "ghi" and the subscriber line number "uvxy".
Thus, it may be appreciated that any central office switch may receive a call having any one of a large number of destination addresses. A central office switch would be easily overwhelmed if it had to keep track of each specific destination address. However, each central office switch need only keep track of the specific destination addresses of the subscriber locations connected thereto via a subscriber line. The remaining calls are typically routed according to their area code or area code and NNX number to another central office switch. This "hierarchical" routing scheme, whereby calls are routed according to only a portion of the destination address, is typically carried out at each central office switch.
At each central office switch, all of the possible destination addresses of calls and packets are organized into a multilevel hierarchy. FIG. 4 depicts an exemplary hierarchy for the central office switch I of FIG. 1. As depicted in FIG. 4, seven destination addresses visible to the central office switch I are shown arranged in a tree structure. Each address has ten digits as before where an X digit indicates a wild card digit which may be any number. The highest level in the hierarchy contains the destination address XXX-XXX-XXXX which matches every possible destination address of a call or packet. The next highest level in the hierarchy contains the destination addresses 908-XXX-XXXX, 201-XXX-XXXX and 212-XXX-XXXX which match each possible destination address having one of three area codes, i.e., 201, 908 or 212. The next highest level in the hierarchy contains the destination addresses 201-829-XXXX and 201-867-XXXX which match each possible destination address within one of two local exchanges within the 201 area code, i.e., 829 or 867. Finally, the lowest level in the hierarchy contains the destination address 201-829-4698 which matches only the destination address having the specific subscriber location 4698 in the local exchange 829 of the area code 201.
In routing a call or packet according to a multilevel hierarchy, the destination address of the call or packet is matched to destination addresses in the hierarchy. The call or packet is then routed onto the output port assigned to the destination address having the lowest level in the hierarchy which matches the destination address of the call or packet. For example, consider a packet with the destination address 201-829-4484. The destination address of this packet matches destination addresses in three levels of the hierarchy, 201-829-XXXX, 201-XXX-XXXX and XXX-XXX-XXXX. The matching destination address on the lowest level of the hierarchy is 201-829-XXXX. In this case, the call or packet destined to the address 201-829-4484 is routed onto an output port assigned to the destination address 201-829-XXXX. Similarly, a call with the destination address 908-829-4698 matches the destination addresses in two levels of the hierarchy, XXX-XXX-XXXX and 908-XXX-XXXX (the entry 201-829-4698 does not match this second address in the hierarchy as any mismatched digits result in a complete mismatch). The matching destination address of the lowest level in the hierarchy is the destination address 908-XXX-XXXX. Thus, the call or packet destined to the address 908-829-4698 is routed onto the output port assigned to the destination address 908-XXX-XXXX.
Illustratively, each central office switch consults a multilevel hierarchical routing table to determine the appropriate output port onto which a received call or packet should be routed. An exemplary multilevel hierarchical routing table (Table 1) is shown below.
TABLE 1 ______________________________________ Address Output Port ______________________________________ 201-829-4698 Port A 201-829-XXXX Port B 201-867-XXXX Port C 201-XXX-XXXX Port D 908-XXX-XXXX Port E 212-XXX-XXXX Port F XXX-XXX-XXXX Port G ______________________________________
The routing table comprises a plurality of pairs. The first element of each pair is a destination address. As depicted, the routing table includes each of the destination addresses of the multilevel hierarchy depicted in FIG. 4. Associated with each destination address is a corresponding output port entry indicating an output port onto which calls or packets destined for the respective destination address should be routed. For example, all packets or calls with a destination address having a 908 area code are routed onto the output port E.
Several conventional methods have been proposed for retrieving the appropriate output port entry from such a multilevel hierarchical routing table. In a first conventional method called linear search, each pair of routing table entries are stored in a memory such as a RAM. To locate the best match, the destination address of each pair stored in the RAM is successively retrieved and compared to the destination address of the call or packet. The call or packet is then routed onto the output port indicated by the output port entry corresponding to the matching destination address entry of the lowest level in the hierarchy. While such a solution is simple and inexpensive, the execution time is on the order of O(N) where N is the number of pairs of entries in the routing table. Thus, as N increases, the execution time of the above method increases in a linear manner.
In a second faster conventional approach, the pairs of destination addresses and output port entries are organized into a tree structure such as a binary tree, patricia tree or trie tree. The time required to search such a tree is of the order of O(log.sub.p N) where the log base p depends on the type of tree used to store the routing table (e.g., for a binary or patricia tree, p=2). The log base p may be increased by selecting a different tree structure for storing the routing table. However, if the destination addresses are sparsely distributed over the domain of possible destination addresses, as is typical for telephone destination addresses, the resulting tree may require an unacceptably large memory. Furthermore, although faster than the first aforementioned routing table implementation, the second solution may still be too slow for use in a high speed central office switch where the allotted search time may be no more than a fraction of the time to transmit a packet on a high speed link.
In a third conventional solution, a hashing function may be used to convert the destination address of the call or packet to an index within a reasonably small range. The index, in turn, may be used as a memory address to access a memory such as a RAM to retrieve a corresponding output port entry. The third solution provides for quick routing table searches for most cases. However, in a worst case scenario, the search time may be greater than the aforementioned tree search solution because the hashing function may produce the same index value for more than one destination address. Furthermore, the execution time of the third solution is a function of the size of the memory used and the number of potential destination addresses which must be searched at any given time. The routing table may be relatively small because of the hierarchical organization of the destination addresses (i.e., the number of routing table entries is on the order of several tens or hundreds). However, the potential number of addresses to be searched can be very large. The number depends on calling traffic patterns which are difficult to predict, especially for emerging data networks. Therefore, the amount of memory or search time for this solution may be very large.
It is also possible to simply use each destination address as a memory address for a RAM. The destination address is inputted on the memory address lines of a RAM and a corresponding output port entry stored in the addressed memory location is retrieved. In this solution, a RAM must be provided which is big enough to have a separately addressable memory location for each conceivable destination address. Thus, the size of such a RAM is extremely large despite having relatively few destination address entries in the routing table.
The prior art has also suggested using a content addressable memory or CAM in a high speed packet switch to translate a packet destination address into an output port. See A. McAuley & C. Cotton, "A Self-Testing Reconfigurable CAM," I.E.E.E. J. of Solid State Circuits, vol 26, no. 3, p. 257-61, Mar., 1991; H. Yamada, Y. Murata, T. Maeda, R. Ikeda, K. Motohashi & K. Takahashi, "Real-Time String Search Engine LSI for 800-Mbit/sec LANs," Proc. I.E.E.E. Custom Integrated Circuits Conference, p. 21.6.1-21.6.4, 1988; L. Chivin & R. Duckworth, "Content Addressable and Associative Memory: Alternatives to the Ubiquitous RAM," I.E.E.E. Computer Magazine, p. 51-64, Jul., 1989. A conventional CAM has the same read and write operations as a RAM. In addition, a CAM has a search operation in which a data entry inputted to the CAM is masked, in part, by a mask. The non-masked portion of this data entry is compared, in parallel, to each entry stored in a memory array of the CAM. If the non-masked bits of the inputted data match corresponding bits of an entry stored in the memory array, the contents of the entry are outputted from the CAM.
A CAM may also be designed so that only a first portion of each entry stored in the memory array is compared to the masked inputted data and so that only a second portion of an entry is outputted if a match occurs. Thus, each entry may contain a first field which is compared to non-masked portions of inputted data and a second field which is outputted if a match occurs. Typically, such a CAM is an address-less CAM, which does not use addresses for writing to or reading from the memory array. Rather, during a write operation, only the data which is to be written in the CAM is inputted thereto. This data is stored in the next available location in the memory array of the CAM. When a search is performed, only a flag is returned if the first field of an entry matches the masked inputted data. However, the CAM keeps track of the matching entry which may be retrieved by executing a read operation (without a memory address) after the search. The advantage of the address-less CAM is that addresses are entirely dispensed with thereby simplifying overall system design.
Although the prior art has suggested using a CAM for translating destination addresses to output ports, there are no conventional implementations of a multilevel hierarchical routing table using a CAM. Thus, the prior art proposals do not provide for routing a call or packet with a destination address that matches several destination address entries in the routing table (of different levels in a hierarchy of destination addresses).
It is therefore an object of the present invention to implement a multilevel hierarchical routing table in a switch. It is another object of the present invention to route calls or packets onto the output port indicated by the output port entry corresponding to the destination address, of the lowest level of the hierarchy, which matches the destination address of the call or packet. It is a further object of the present invention to provide a fast implementation, which conserves storage space, for routing calls and packets through a switch according to a multilevel hierarchy of destination addresses.